package problems.contest;

import java.util.Arrays;

/**
 * <p></p>
 *
 * @author habitplus
 * @since 2023/3/5 14:44
 */
public class BCT99 {

    /**
     * T3| 6313. 统计将重叠区间合并成组的方案数
     * <p>https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/</p>
     */
    public int countWays(int[][] ranges) {

        int n = ranges.length;
        final int MOD = (int) (1e9 + 7);
        // 统计无交集区间的组数
        int group = 0;
        int r = Integer.MIN_VALUE;
        // 对于每个独立的区间组，都可以选择放入a组或b组，故答案就是 2^group
        long res = 1L;

        Arrays.sort(ranges, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);

        for (int i = 0; i < n; ++i) {
            if (ranges[i][0] > r) {
                ++group;
                res = (res * 2) % MOD;
                r = ranges[i][1];
                continue;
            }
            r = Math.max(r, ranges[i][1]);
        }

        return (int) res;
    }

    public static void main(String[] args) {
        BCT99 test = new BCT99();
        int[][] arr = {{5, 11}, {20, 22}, {1, 3}, {21, 22}, {11, 11}};
        System.out.println(test.countWays(arr));
    }
}
